package insertSort;

/**
 * Created with IntelliJ IDEA.
 * Description: 插入排序
 * User: 86187
 * Date: 2022-08-09
 * Time: 20:34
 */
public class MyInsertSort {

    /**
     *  直接插入排序:
     *  时间复杂度：最坏：O(N^2)  最好：O(N)
     *         --->结论：对于直接插入排序来说，数据越有序越快
     *         --->场景：当数据基本有序的时候，使用直接插入排序
     *  空间复杂度：O(1)
     *  稳定性:稳定
     *        一个本身就稳定的排序，你可以实现为不稳定
     *        但是一个本身不稳定的排序，你没有办法变成稳定的排序
     */
    public void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {

                //加上等号就变成不稳定，但算法本身还是有序的
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
}
